package com.zjsru.plan2023.oneday;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: cookLee
 * @Date: 2023-09-10
 * 课程表
 */
public class CanFinish {

    /**
     * 输入：numCourses = 2, prerequisites = [[1,0]]
     * 输出：true
     * 解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
     *\
     * 输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
     * 输出：false
     * 解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
     *
     * */
    public static void main(String[] args) {
        CanFinish canFinish = new CanFinish();
        int numCourses = 2;
        int[][] prerequisites = new int[][]{{1, 0}};
        System.out.println(canFinish.canFinish(numCourses, prerequisites));
    }

    /**
     * 存储有向图
     */
    List<List<Integer>> edges;

    /**
     * 标记每个节点的状态
     */
    int[] visited;

    /**
     * 是否可以
     */
    boolean valid = true;

    /**
     * 深度搜索
     * @param numCourses
     * @param prerequisites
     * @return boolean
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<Integer>());
        }
        visited = new int[numCourses];
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]);
        }
        //遍历找到一个为搜索的节点， dfs
        for (int i = 0; i < numCourses && valid; i++) {
            if (visited[i] == 0) {
                this.dfs(i);
            }
        }
        return valid;
    }

    /**
     * 深度优先搜索
     * @param i
     */
    private void dfs(int i) {
        //节点标记为 搜索中
        visited[i] = 1;
        //搜索相邻节点
        //发现有环 停止搜索
        for (int v : edges.get(i)) {
            //存在 未搜索 搜索相邻节点
            if (visited[v] == 0) {
                this.dfs(v);
                if (!valid) {
                    return;
                }
            }
            //如果 搜索中 找到了环
            else if (visited[v] == 1) {
                valid = false;
                return;
            }
        }
        //节点标记为 已完成
        visited[i] = 2;
    }
}
